package a2022.a20220919;

import java.util.*;

/**
 * @author lenovo
 * @date 2022/9/19
 */
public class a {
    public static void main(String[] args) {
        //5,-1,4,4,-6,-6,1,1,1
        System.out.println(Arrays.toString(frequencySort(new int[]{1, 1, 2, 2, 2, 3})));
        System.out.println(Arrays.toString(frequencySort2(new int[]{1, 1, 2, 2, 2, 3})));
    }

    public static int[] frequencySort(int[] nums) {
        int length = nums.length;
        int[] is = new int[length];
        Arrays.sort(nums);
        int n = nums[0];
        List<int[]> list = new ArrayList<>();
        //计数
        int num = 0;
        int x = 0;
        for (int i = 0; i < length; i++) {
            if (nums[i] == n) {
                num++;
            } else {
                x = i;
                int[] arr = new int[]{num, nums[i - 1]};
                list.add(arr);
                n = nums[i];
                num = 1;
            }
        }
        int[] arr = new int[]{length - x, nums[length - 1]};
        list.add(arr);
        Collections.sort(list, (l1, l2) -> {
            return l1[0] != l2[0] ? l1[0] - l2[0] : l2[1] - l1[1];
        });
        num = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int i1 = 0; i1 < list.get(i)[0]; i1++) {
                is[num] = list.get(i)[1];
                num++;
            }
        }

        return is;
    }

    public static int[] frequencySort2(int[] nums) {
        int[] value1 = new int[201];
        for (int num : nums) {
            value1[num+100]++;
        }
        List<Integer>[] lists = new ArrayList[101];
        for (int i = 200; i >= 0; i--) {
            int value = value1[i];
            if (value == 0) {
                continue;
            }
            List<Integer> list = lists[value];
            if (list == null) {
                list = new ArrayList<>();
                lists[value] = list;
            }
            list.add(i - 100);
        }
        int i = 0;
        int v;
        for (int j = 0; j < 101; j++) {
            List<Integer> list = lists[j];
            if (list == null) {
                continue;
            }
            for (int k : list) {
                v = j;
                while(v > 0) {
                    nums[i++] = k;
                    v--;
                }
            }
        }
        return nums;
    }

    public int[] frequencySort3(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        Arrays.stream(nums).forEach(x -> counts.put(x, counts.getOrDefault(x, 0) + 1));
        return Arrays.stream(nums).boxed().sorted((x, y) -> counts.get(x).equals(counts.get(y)) ? y - x : counts.get(x) - counts.get(y)).mapToInt(Integer::intValue).toArray();
    }

}
